import { BSTree } from "./00_二叉搜索树BSTree";
import { AVLTreeNode } from "./04_封装AVLTheeNode(左旋转操作)";

class AVLTree<T> extends BSTree<T> {
  // 重写调用createNode方法
  protected createNode(data: T): AVLTreeNode<T> {
    return new AVLTreeNode(data);
  }

  // 检查不平衡的节点
  protected checkBalanced(node: AVLTreeNode<T>, isAdd = true) {
    let current = node.parent as AVLTreeNode<T>;
    while (current) {
      if (!current.isBalanced) {
        this.rebalance(current);

        if (isAdd) break;
      }

      current = current.parent as AVLTreeNode<T>; // 向上移动
    }
  }

  /**
   * rebalance: 再平衡树结构
   * @param root 不平衡的根节点
   */
  rebalance(root: AVLTreeNode<T>) {
    const pivot = root.getHigherChild; // 获取更高的子节点
    const current = pivot?.getHigherChild; // 获取更高的子节点的更高的子节点

    let resultNode: AVLTreeNode<T> | null = null;
    if (pivot?.isLeft) {
      if (current?.isLeft) {
        // 左左情况
        resultNode = root.rightRotation();
      } else {
        // 右左情况
        pivot.leftRotation();
        resultNode = root.rightRotation();
      }
    } else {
      if (current?.isRight) {
        // 右右情况
        resultNode = root.leftRotation();
      } else {
        // 左右情况
        pivot?.rightRotation();
        resultNode = root.leftRotation();
      }
    }

    // 如果pivot的current为null，则说明是根节点，让root指向resultNode
    if (!pivot?.parent) {
      this.root = resultNode;
    }
  }
}

const avlTree = new AVLTree<number>();

const nums: number[] = [];

for (let i = 0; i < 20; i++) {
  const num = Math.floor(Math.random() * 200);
  if (i < 10) nums.push(num);
  avlTree.insert(num);
}

avlTree.print();

for (const item of nums) {
  console.log("删除节点", item);
  avlTree.remove(item);
}

console.log(nums);

export {};
